package leetcode.editor.cn;

import java.util.Stack;

/**
 * @Author: Dempsey
 * @Data: 2021-01-05 14:59:26
 */

//给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。 
//
// 有效字符串需满足： 
//
// 
// 左括号必须用相同类型的右括号闭合。 
// 左括号必须以正确的顺序闭合。 
// 
//
// 注意空字符串可被认为是有效字符串。 
//
// 示例 1: 
//
// 输入: "()"
//输出: true
// 
//
// 示例 2: 
//
// 输入: "()[]{}"
//输出: true
// 
//
// 示例 3: 
//
// 输入: "(]"
//输出: false
// 
//
// 示例 4: 
//
// 输入: "([)]"
//输出: false
// 
//
// 示例 5: 
//
// 输入: "{[]}"
//输出: true 
// Related Topics 栈 字符串 
// 👍 2074 👎 0


public class P20 {
    public static void main(String[] args) {
        Solution solution = new P20().new Solution();
        solution.isValid("()");
    }

    // () 40,41
    // [] 91,93
    // () 123,125

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public boolean isValid(String s) {
            if (s == null || s.equals("")) return false;

            char[] chars = s.toCharArray();

            Stack<Character> characterStack = new Stack<>();

            for (char c : chars) {
                if (characterStack.empty()) {
                    characterStack.push(c);
                    continue;
                }
                Character peek = characterStack.peek();
                if ((peek == 40 && c == 41) || (peek == 91 && c == 93) || (peek == 123 && c == 125)) {
                    characterStack.pop();
                    continue;
                }
                if ((peek == 40 && (c == 93 || c == 125)) || (peek == 91 && c == 125)) {
                    return false;
                }
                characterStack.push(c);
            }

            return characterStack.empty();

        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}